package com.jia.leetCode;

import java.util.Arrays;

public class Pro0085 {
    static class Rectangle{
        int x; //宽
        int y; //高
        public Rectangle(int x, int y) {this.x = x; this.y = y; }
        public int getS(){
            return x * y;
        }
        public String toString(){
            return getS()+"";
        }
    }
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int n = matrix.length, m = matrix[0].length;
        //f[i][j]以i，j为正方形右下角固定的最大正方形
        Rectangle[][] f = new Rectangle[n][m];
        int ans = 0;//最大面积
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] == '0') {
                    f[i][j] = new Rectangle(0, 0);
                }else {
                    f[i][j] = new Rectangle(1, 1);
                    if(i > 0 && j > 0){
                        //三个正方形最小面积 + 1
                        //如果求矩形的最大值的话
                        //f[i-1][j] 矩形 A
                        //f[i-1][j-1] 矩形B
                        //f[i][j-1]   矩形C
                        //求f[i][j] 矩形D最大面积
                        //设f[i][j]有宽和高属性(x,y),那么只需求D.x和D.y的最大值即可 D.x = min(C.x,B.x)+1, D.y = min(A.y,B.y)+1,最大面积就是D.x * D.y即可
                        f[i][j].x += Math.min(f[i][j - 1].x, f[i-1][j-1].x);
                        f[i][j].y += Math.min(f[i-1][j].y, f[i-1][j-1].y);
                    }else if(i > 0 && j == 0) {
                        f[i][j].y += f[i-1][j].y;
                    }else if(j > 0 && i == 0) {
                        f[i][j].x += f[i][j-1].x;
                    }
                    if(f[i][j].getS() > ans) {
                        ans = f[i][j].getS();
                    }
                }
            }
        }
        for(int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(f[i]));
        }
        return ans;
    }

    public static void main(String[] args) {
        char[][] matrix = {{'0','1'},{'0', '1'}};
        Pro0085 pro0085 = new Pro0085();
        pro0085.maximalRectangle(matrix);
    }
}
